package sort.choose_sort;

import java.util.Arrays;

/**
 * 堆是一颗完全二叉树 <br />
 * 时间复杂度恒定为 O(nlogn) <br />
 * 建堆的时间复杂度: O(n) <br />
 * 不稳定, 例如 (0, 2), (1, 1), (2, 1), 第一个元素跟最后一个元素交换后, (2, 1), (1, 1), (0, 2) <br />
 * <p>大顶堆(从 0 开始)：arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 1]</p>
 * <p>小顶堆(从 0 开始)：arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 1]</p>
 * <p>升序：构造一个大顶堆，然后将根节点与最后一个叶子节点交换，这样根节点就在数组的最后一个位置了，继续重构大顶堆，重复以上步骤
 * 1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
 * 2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为 n-1
 * 3.将剩余的 n-1个数再构造成大根堆，再将顶端数与 n-1位置的数交换，如此反复执行，便能得到有序数组
 * <p>参考：
 * https://www.cnblogs.com/chengxiao/p/6129630.html
 * https://blog.csdn.net/qq_28063811/article/details/93034625</p>
 * <p>堆的操作</p>
 * <p>添加元素：新加的元素放到最后一个位置, 然后将元素“上升”</p>
 * <p>删除元素：删除元素的位置用最后一个元素代替, 然后代替的元素“下坠”</p>
 *
 * @author yzh
 * @version 1.0
 * @date 2022/4/25 16:45
 */
public class HeapSort {
    public static void main(String[] args) {
//        int[] arr = new int[]{29, 10, 200, 1, 0};
//        int[] arr = {0, 20, -1, 10, 100, 30, -6};
//        int[] arr = {3, -44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        int[] arr = {0, 3, -44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        anotherHeapSort(arr, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int n = arr.length;
        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--)
            // 从第一个非叶子节点从从下至上，从右往左调整结构
            adjustHeap(arr, i, n);
        // 调整堆结构 + 交换堆顶元素与末尾元素
        for (int i = n - 1; i > 0; i--) {
            // 将堆顶元素与末尾元素进行交换
            swap(arr, 0, i);
            // 重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }

    public static void adjustHeap(int[] arr, int i, int len) {
        // 取出当前元素
        int tmp = arr[i];
        // k = 2 * i + 1, 从 i 节点的左子节点开始
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            // 如果左子节点 < 右子节点，则指向右子节点
            if (k + 1 < len && arr[k] < arr[k + 1]) ++k;
            // 如果子节点大于父节点，将子节点的值赋值给父节点
            if (arr[k] > tmp) {
                arr[i] = arr[k];
                arr[k] = tmp; // 这步不用写也行
                // 如果子节点变了，那么子节点的子节点可能也要改变
                i = k;
            } else break;
        }
        arr[i] = tmp;
    }

    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) adjustHeapRecursion(arr, i, n);
        // 堆排序
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            adjustHeapRecursion(arr, 0, i);
        }
    }

    public static void adjustHeapRecursion(int[] arr, int i, int n) {
        int idx = i;
        if (i * 2 + 1 < n && arr[i * 2 + 1] > arr[idx]) idx = i * 2 + 1;
        if (i * 2 + 2 < n && arr[i * 2 + 2] > arr[idx]) idx = i * 2 + 2;
        if (idx != i) {
            swap(arr, i, idx);
            adjustHeapRecursion(arr, idx, n);
        }
    }

    /**
     * 书上的写法
     * <p>第一个位置空着, 元素从下标为 1 的位置开始存</p>
     * <p>所以, 第 i 个位置的左孩子为 2 * i, 右孩子为 2 * i + 1</p>
     */
    public static void anotherHeapSort(int[] arr, int n) {
        // 从倒数第一个非叶子结点开始建立大顶堆
        for (int i = n / 2; i >= 1; i--) anotherAdjustHeap(i, arr, n);
        for (int i = n; i > 1; i--) {
            // 这一步导致排序不稳定, 例如 2, 1, 1 -> 1, 1, 2
            swap(arr, 1, i);
            anotherAdjustHeap(1, arr, i - 1);
        }
    }

    private static void anotherAdjustHeap(int k, int[] arr, int n) {
        arr[0] = arr[k];
        for (int i = 2 * k; i <= n; i = 2 * i) {
            if (i < n && arr[i] < arr[i + 1]) ++i;
            if (arr[0] < arr[i]) {
                arr[k] = arr[i];
                // 小元素下坠
                k = i;
            } else break;
        }
        arr[k] = arr[0];
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
